Description

$\text{Link}$

Solution

网络流解方程。

刚了一道题超级久...最后 solution 给的做法是 FWT 。觉得做法还挺妙的。
顺带讲讲对 FWT 的理解，怕自己又不记得了。

原理

Description

给定两个 $1\sim n$ 的排列 $p$ 和 $q$ ，其中有些位置未知，用 $0$ 表示。
定义两个排列之间的相似度是：每次从 $p$ 中选择两个元素交换，使其变成 $q$ 的最小次数。
现在要求不全这两个序列，求出对于 $i\in [0,n-1]$ ，补全后相似度为 $i$ 的方案数。

Description

给定长度为 $n$ 的序列 $\{a\}$ ，求 $\{a\}$ 有多少种排列，满足任意相邻两个数的乘积不是完全平方数。
答案对 $10^9+7$ 取模。
$n\leq 300$

Description

有 $n$ 个物品，每个物品有一个权值 $w_i$ 。
现在你需要把这 $n$ 个物品划分成 $k$ 个非空集合。
定义在一个划分下物品的价值为权值和所在集合大小的乘积，一个划分的价值为所有物品的价值之和。

Description

给定一个 $n\times m$ 的网格，计算三个点都在格点上的三角形共有多少个。三角形的三点不能共线。
$n,m\leq 10^3$

Solution

Description

给定一棵有 $n$ 个节点的树。求对于每个 $k\in[0,n-1]$，有多少棵由这 $n$ 个点之间的边构造成的树，与给定的树恰好有 $k$ 条边重复。答案对 $10^9+7$ 取模。
$n\leq 100$

Solution

Description

给定 $n$ 个数 $a_1,\cdots, a_n$ ，求两两 $\text{lcm}$ 的最大值。
$1\leq n,a_i\leq 10^5$

Solution

Description

题面挺长的所以挂个链接

Solution

首先观察一下题面：它的值域不大。

Description

题面挺长挂个链接

Solution

「所有的鸽子都饱了」本质就是求每个鸽子第一次饱的时刻的最大值嘛，由于第一次本应是「最小」的含义，所以最值反演一手。